import heapq
from collections import defaultdict
from typing import List

MOD = 10 ** 9 + 7


class Solution:
    def countPaths(self, n: int, roads: List[List[int]]) -> int:
        # 构造无向加权图
        graph = defaultdict(dict)
        for edge in roads:
            power = edge[2] if edge[1] not in graph[edge[0]] else min(graph[edge[0]][edge[1]], edge[2])
            graph[edge[0]][edge[1]] = graph[edge[1]][edge[0]] = power

        # 到达某个地点最早时间 [到达时间,到达地点]
        heap = [[0, 0]]

        # 到达某个地点的方案数 {到达地点:方案数量}
        res_num = {0: 1}

        # 到达某个地点的最早时间 {到达地点:到达最早时间}
        res_time = {0: 0}

        while heap:
            t1, n1 = heapq.heappop(heap)

            # 如果不是到达当前位置的最短时间
            if res_time[n1] < t1:
                continue

            # 如果已经不可能出现更优的到达目的地的方案
            if n - 1 in res_num and res_time[n - 1] < t1:
                break

            for n2 in graph[n1]:
                t2 = t1 + graph[n1][n2]
                if n2 not in res_time:
                    res_time[n2] = t2
                    res_num[n2] = res_num[n1]
                    heapq.heappush(heap, [t2, n2])
                elif res_time[n2] > t2:
                    res_time[n2] = t2
                    res_num[n2] = res_num[n1]
                    heapq.heappush(heap, [t2, n2])
                elif res_time[n2] == t2:
                    res_num[n2] += res_num[n1]

        return res_num[n - 1] % MOD


if __name__ == "__main__":
    # 4
    print(Solution().countPaths(n=7, roads=[[0, 6, 7], [0, 1, 2], [1, 2, 3], [1, 3, 3], [6, 3, 3], [3, 5, 1], [6, 5, 1],
                                            [2, 5, 1], [0, 4, 5], [4, 6, 2]]))

    # 1
    print(Solution().countPaths(n=2, roads=[[1, 0, 10]]))

    # 测试用例16/54
    #
    print(Solution().countPaths(n=30,
                                roads=[[0, 1, 4233], [1, 2, 5402], [0, 3, 17153], [2, 3, 7518], [3, 1, 12920],
                                       [0, 4, 25], [0, 5, 26859], [5, 2, 17224], [5, 4, 26834], [5, 1, 22626],
                                       [3, 5, 9706], [6, 5, 1669], [6, 2, 18893], [0, 6, 28528], [6, 3, 11375],
                                       [6, 4, 28503], [6, 1, 24295], [7, 2, 3378], [0, 8, 36208], [8, 4, 36183],
                                       [6, 8, 7680], [0, 9, 46027], [4, 9, 46002], [9, 7, 33014], [2, 9, 36392],
                                       [9, 8, 9819], [9, 6, 17499], [9, 3, 28874], [9, 1, 41794], [9, 10, 5734],
                                       [5, 10, 24902], [2, 10, 42126], [1, 10, 47528], [10, 8, 15553], [7, 10, 38748],
                                       [9, 11, 8417], [11, 3, 37291], [10, 11, 2683], [6, 11, 25916], [11, 4, 54419],
                                       [12, 7, 47736], [3, 12, 43596], [5, 12, 33890], [10, 12, 8988], [12, 6, 32221],
                                       [11, 12, 6305], [12, 1, 56516], [12, 2, 51114], [13, 1, 60560], [2, 13, 55158],
                                       [13, 11, 10349], [13, 4, 64768], [0, 13, 64793], [9, 13, 18766], [13, 6, 36265],
                                       [7, 13, 51780], [13, 10, 13032], [12, 13, 4044], [5, 13, 37934], [3, 13, 47640],
                                       [8, 14, 32645], [14, 4, 68828], [0, 14, 68853], [7, 14, 55840], [14, 3, 51700],
                                       [14, 5, 41994], [14, 13, 4060], [11, 14, 14409], [5, 15, 50783], [8, 15, 41434],
                                       [15, 9, 31615], [15, 14, 8789], [4, 15, 77617], [15, 6, 49114], [0, 15, 77642],
                                       [2, 15, 68007], [12, 15, 16893], [1, 15, 73409], [15, 13, 12849], [15, 3, 60489],
                                       [7, 15, 64629], [11, 15, 23198], [15, 10, 25881], [16, 13, 20123],
                                       [16, 1, 80683], [15, 16, 7274], [16, 0, 84916], [16, 6, 56388], [16, 3, 67763],
                                       [17, 3, 75033], [17, 15, 14544], [0, 17, 92186], [1, 17, 87953], [17, 5, 65327],
                                       [2, 17, 82551], [17, 13, 27393], [16, 17, 7270], [17, 4, 92161], [17, 10, 40425],
                                       [14, 17, 23333], [17, 12, 31437], [17, 9, 46159], [18, 7, 80595], [18, 3, 76455],
                                       [5, 18, 66749], [8, 18, 57400], [9, 18, 47581], [11, 18, 39164], [4, 18, 93583],
                                       [18, 17, 1422], [18, 12, 32859], [0, 18, 93608], [15, 18, 15966], [16, 18, 8692],
                                       [14, 18, 24755], [6, 18, 65080], [19, 16, 12261], [15, 19, 19535],
                                       [19, 7, 84164], [19, 18, 3569], [19, 6, 68649], [8, 19, 60969], [19, 1, 92944],
                                       [5, 19, 70318], [10, 19, 45416], [19, 11, 42733], [2, 19, 87542],
                                       [20, 13, 33827], [20, 15, 20978], [20, 0, 98620], [20, 16, 13704],
                                       [10, 20, 46859], [20, 14, 29767], [20, 3, 81467], [18, 20, 5012],
                                       [12, 20, 37871], [20, 8, 62412], [20, 4, 98595], [20, 11, 44176], [2, 20, 88985],
                                       [1, 20, 94387], [20, 5, 71761], [19, 20, 1443], [16, 21, 19446], [17, 21, 12176],
                                       [0, 21, 104362], [21, 7, 91349], [8, 21, 68154], [21, 3, 87209], [18, 21, 10754],
                                       [21, 20, 5742], [1, 21, 100129], [21, 6, 75834], [10, 21, 52601], [21, 19, 7185],
                                       [12, 21, 43613], [21, 14, 35509], [21, 2, 94727], [22, 20, 2033], [22, 2, 91018],
                                       [12, 23, 47214], [4, 23, 107938], [23, 20, 9343], [23, 0, 107963],
                                       [23, 15, 30321], [2, 24, 21315], [3, 24, 13797], [1, 24, 26717], [5, 24, 4091],
                                       [25, 13, 46183], [6, 25, 82448], [25, 12, 50227], [25, 4, 110951],
                                       [25, 19, 13799], [25, 9, 64949], [25, 15, 33334], [25, 21, 6614],
                                       [0, 25, 110976], [25, 8, 74768], [1, 25, 106743], [3, 25, 93823],
                                       [14, 25, 42123], [25, 17, 18790], [5, 26, 93928], [17, 26, 28601],
                                       [9, 26, 74760], [26, 25, 9811], [4, 26, 120762], [26, 6, 92259], [21, 26, 16425],
                                       [11, 26, 66343], [8, 26, 84579], [9, 27, 78280], [27, 17, 32121],
                                       [10, 27, 72546], [3, 27, 107154], [19, 27, 27130], [11, 27, 69863],
                                       [5, 27, 97448], [27, 12, 63558], [27, 21, 19945], [24, 27, 93357],
                                       [27, 0, 124307], [27, 22, 23654], [27, 23, 16344], [4, 27, 124282],
                                       [27, 26, 3520], [27, 16, 39391], [2, 27, 114672], [13, 27, 59514],
                                       [7, 27, 111294], [25, 27, 13331], [27, 1, 120074], [8, 27, 88099],
                                       [27, 14, 55454], [27, 18, 30699], [15, 27, 46665], [20, 27, 25687],
                                       [9, 28, 77263], [28, 7, 110277], [28, 15, 45648], [25, 28, 12314],
                                       [28, 13, 58497], [28, 26, 2503], [28, 0, 123290], [5, 28, 96431], [28, 8, 87082],
                                       [4, 28, 123265], [28, 3, 106137], [28, 17, 31104], [28, 11, 68846],
                                       [20, 28, 24670], [12, 28, 62541], [14, 28, 54437], [28, 22, 22637],
                                       [28, 10, 71529], [6, 28, 94762], [15, 29, 53502], [29, 28, 7854],
                                       [2, 29, 121509], [29, 19, 33967], [3, 29, 113991], [29, 14, 62291],
                                       [29, 25, 20168], [29, 8, 94936], [29, 21, 26782], [29, 27, 6837],
                                       [5, 29, 104285], [29, 13, 66351], [29, 18, 37536], [23, 29, 23181],
                                       [11, 29, 76700], [4, 29, 131119], [29, 20, 32524], [7, 29, 118131],
                                       [17, 29, 38958], [26, 29, 10357]]))
